from collections import defaultdict

# 只考虑简单图

class DenseGraph:
    def __init__(self, n, directed=False):
        self.n = n  # 顶点数
        self.m = 0  # 边数 - 初始为0
        self.directed = directed  # 是否为有向图
        # 使用邻接矩阵表示图
        self._graph = [[0]*n for i in range(n)]
    
    def V(self):
        return self.n
    
    def E(self):
        return self.m

    def add_edge(self, v, w):
        assert v >= 0 and v < self.n
        assert w >= 0 and w < self.n

        # 已经存在这条边什么也不做，避免平行边
        if self.has_edge(v, w):
            return
        
        self._graph[v][w] = 1
        if not self.directed:
            self._graph[w][v] = 1
        
        self.m += 1
    
    def has_edge(self, v, w):
        assert v >= 0 and v < self.n
        assert w >= 0 and w < self.n
        return bool(self._graph[v][w])

    def __str__(self):
        ret = ''
        for item in self._graph:
            ret += str(item) + '\n'
        return ret.rstrip()  # 去掉最后一个'\n'

class SparseGraph:
    def __init__(self, n, directed=False):
        self.n = n  # 顶点数
        self.m = 0  # 边数 - 初始为0
        self.directed = directed  # 是否为有向图
        # 使用邻接表表示图
        self._graph = defaultdict(list)  # 顶点 -> [顶点, ...]

    def V(self):
        return self.n
    
    def E(self):
        return self.m

    def add_edge(self, v, w):
        assert v >= 0 and v < self.n
        assert w >= 0 and w < self.n

        # O(n)复杂度 - 避免平行边
        if self.has_edge(v, w):
            return

        self._graph[v].append(w)

        # 如果v和w相等，那么为自环边
        if v != w and not self.directed:
            self._graph[w].append(v)
        
        self.m += 1
    
    def has_edge(self, v, w):
        assert v >= 0 and v < self.n
        assert w >= 0 and w < self.n

        # 遍历与v相邻的所有边，看是否有w
        for u in self._graph[v]:
            if u == w:
                return True
        return False

    def __str__(self):
        return str(self._graph)

    # 获取顶点v对应的邻边
    def edges(self, v):
        for u in self._graph[v]:
            yield u

def build_graph(filename, num_vertices):
    graph = SparseGraph(num_vertices)
    with open(filename) as f:
        for line in f:
            u, v = line.strip().split()
            u = int(u)
            v = int(v)
            graph.add_edge(u, v)

    return graph

if __name__ == '__main__':
    #    0 1 2 3
    # 0  0 1 0 1
    # 1  1 0 1 0
    # 2  0 1 0 1
    # 3  1 0 1 0
    graph1 = DenseGraph(4, directed=True)
    graph1.add_edge(0, 1)
    graph1.add_edge(0, 3)
    graph1.add_edge(1, 0)
    graph1.add_edge(1, 2)
    graph1.add_edge(2, 1)
    graph1.add_edge(2, 3)
    graph1.add_edge(3, 0)
    graph1.add_edge(3, 2)
    print(graph1)

    graph2 = SparseGraph(4, directed=True)
    graph2.add_edge(0, 1)
    graph2.add_edge(0, 3)
    graph2.add_edge(1, 0)
    graph2.add_edge(1, 2)
    graph2.add_edge(2, 1)
    graph2.add_edge(2, 3)
    graph2.add_edge(3, 0)
    graph2.add_edge(3, 2)
    print(graph2)